//200. 岛屿数量

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    if(grid.length===0) return 0;
    var ans =0;
    var visited = [];
    var row = grid.length;
    var col = grid[0].length;
    for(var i= 0;i<row;i++){
        visited.push(new Array(col));
        for(var j=0;j<col;j++){
            visited[i][j] = false;
        }
    }
    
    for(var i= 0;i<row;i++){
        for(var j=0;j<col;j++){
            if(visited[i][j]===false&&'1'===grid[i][j]){
                dfs(grid,visited,i,j);
                ans++;
            }
        }
    }
    return ans;
};


/**
 * 
 * @param {character[][]} grid 地图 
 * @param {boolean[]} visited 是否被访问
 * @param {number} i 开始的横坐标
 * @param {number} j 开始的纵坐标 
 */
function dfs(grid, visited, i, j) {
    visited[i][j] = true;
    var row = grid.length;
    var col = grid[0].length;
    if (i == row - 1 && col == col - 1)return;
    //向右
    if (j != col - 1 && grid[i][j + 1] === '1' && visited[i][j + 1] === false) {
        dfs(grid, visited, i, j + 1);
    }
    //向下
    if (i != row - 1 && grid[i + 1][j] === '1' && visited[i + 1][j] === false) {
        dfs(grid, visited, i + 1, j);
    }
    //向左
    if (i != 0 && grid[i - 1][j] === '1' && visited[i - 1][j] === false) {
        dfs(grid, visited, i - 1, j);
    }
    //向上
    if (j != 0 && grid[i][j-1] === '1' && visited[i][j-1] === false) {
        dfs(grid, visited, i, j-1);
    }
}


grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
    ];


console.log(numIslands(grid));